package com.hr.剑指offer.work1;

/**
 * @author 周恒哲
 * @date 2020/06/17
 **/
public class 面试题68_I_二叉搜索树的最近公共祖先 {

    /**
     * 迭代法
     * 题解：要么q,p都在左，那么我只需要遍历左节点，要么q,p都在右，那么我只需要遍历右节点，反之，在左右两边，输出根节点
     * 方法一：迭代
     * 循环搜索： 当节点 rootroot 为空时跳出；
     * 当 p, qp,q 都在 rootroot 的 右子树 中，则遍历至 root.rightroot.right ；
     * 否则，当 p, qp,q 都在 rootroot 的 左子树 中，则遍历至 root.leftroot.left ；
     * 否则，说明找到了 最近公共祖先 ，跳出。
     * 返回值： 最近公共祖先 rootroot 。
     * 复杂度分析：
     * 时间复杂度 O(N)O(N) ： 其中 NN 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 \log NlogN （满二叉树），最大为 NN （退化为链表）。
     * 空间复杂度 O(1)O(1) ： 使用常数大小的额外空间。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val < p.val && root.val < q.val) {//p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            } else if (root.val > p.val && root.val > q.val) {
                root = root.left;//遍历左节点
            } else {
                break;
            }
        }
        return root;
    }
    //递归
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val < p.val && root.val < q.val){
            return lowestCommonAncestor1(root.right,p,q);
        }
        if (root.val > p.val && root.val > q.val){
            return lowestCommonAncestor1(root.left,p,q);
        }
        return root;
    }
}
